package com.base.greedy;

import java.util.Arrays;

/**
 * @ClassName: NumRescueBoats
 * @Description: 881. 救生艇
 * 第i个人的体重为people[i]，每艘船可以承载的最大重量为limit。
 * <p>
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为limit。
 * <p>
 * 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/boats-to-save-people
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/26 7:03 下午
 */
public class NumRescueBoats {
    /**
     * 贪心策略：应该尽可能两人一船
     * 1、考虑最轻的人和最重的人的体重与限制体重的对比，如果这样都不能乘船，那么最重的人只能独自一人；
     * 2、如果最轻的人和最重的人都可以一起，那么他与任何一个人都可以在一起。所以出于最好的选择，我们将最重和最轻的人放在一起（假如不在一起，那么比如最重和第二轻的人在一起，那么可能导致无法乘坐一船）
     * @param people 重量
     * @param limit  船的限制
     * @return 船数
     */
    public int numRescueBoats(int[] people, int limit) {
        // 先对数组排序
        Arrays.sort(people);
        // 存储需要的船数
        int n = 0;

        //双指针[left,right]
        int left = 0, right = people.length - 1;
        while (left <= right) {
//            if (people[right] == limit){
//                n++;
//                right--;
//            }else {
//                if (people[left]+people[right]<=limit){
//                    right--;
//                    left++;
//                    n++;
//                }else {
//                    right--;
//                    n++;
//                }
//            }
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            n++;
        }
//        if (left == right){
//            return n+1;
//        }
        return n;
    }
}
